perm filename CACHE.2[AM,DBL]1 blob
sn#410724 filedate 1979-01-18 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00004 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 COGNITIVE ECONOMY
C00012 00003 Mail from RAND-UNIX rcvd at 7-Nov-78 1626-PST
C00016 00004 ∂18-Nov-78 1848 DBL Caching
C00027 ENDMK
C⊗;
COGNITIVE ECONOMY
Douglas B. Lenat, Stanford University
Frederick Hayes-Roth, Rand Corporation
Phil Klahr, Rand Corporation
ABSTRACT
Intelligent systems can explore only tiny subsets of their potential
external and conceptual worlds. They must develop efficient forms
of representation, access, and operation to increase their capacities.
Some of these forms involve abstraction, caching, and expectation-
simplified processing. These capabilities in turn can combine to
provide extremely powerful increases in performance. For example,
all three can combine to simplify simulation or, one of its
related functions, detection of surprising events. Our
analysis of the economic principles of modern AI systems or
(presumably more sophisticated) human intelligence suggests that
previous ideas regarding cognitive efficiency have erred in
fundamental ways. For example, the nonredundant storage of
properties in hierarchical inheritance nets increases many processing
costs while providing minimal storage cost savings. We propose
methods to exploit the potential advantages of both schemes.
INTRODUCTION
1. Introduction
Our model of intelligent system organization
Concepts, heuristics, PDIS
Our model of intelligence: knowledge and its expansion (through
experimentation, discovery, conjecture, conditioning)
Our model of computing:
Cheap storage, expensive knowledge acquisition, limited
computing cycles
The problem:
Want to develop initial systems quickly and then have
them speed up and economize their computing to maximize
their potential
The principal ideas:
Abstraction
Caching
Expectation-simplified computing
e.g., ignoring expcted data
giving priority to surprising data
feeding back to confirmed/disconfirmed predictions
Outline of the rest of the paper
2. Abstraction
Desirability of being able to compute rough answers cheaply
Conceptual hierarchies
Heuristic Hierarchies
Interpretation and planning at levels of abstraction
Eg., rules of bomber simulation at difft levels
(this example will ultimately be used to suggest
caching for simplification)
Related research
3. Caching
Modifying memory to save computed results to speed subsequent accesses
Generalization of hardware concept
EURISKO types of caching, as first examples
Contrast with psychological conjectures of cognitive economy
(e.g., Collins&Quillian, KRL, ...). More like HR↑2 Plasticity
model of storing all retrieved paths as direct links
General principles
Updating Principles
-------------------
When
Why
How
get demon traps that flag the cache as out of date
the user requests updating if the cache seems staleness
Where
In what form
What
When not to
How to
Storage Principles
------------------
When
Every time you have to call a lower order function to eval. it
& it took quite a while.
You've caled it before, recently & the value didn't change.
Why
Cost of recomputing vs. cost of storage.
Context of subsequent cals is similar enough (e.g.l, the same
arguments will come up again.
How
Called functions might suggest how to cache their value in higher
calling caches (e.g., my value changes often so cache my defn.).
Cache should be transparent & discardable (should be able to throw
them all away if space needed).
Where
In what form
value ) what level of abstraction (partially evaluated
expression) symbolic expression)
Stack previous values to enable you to tell if they're changing.
What
You store a flag saying you've been here before.
When it was computed.
How much effort was expended on it, down to what levels of
algorithms, with what around caches incorporated.
Certainty of the result.
When not to
The value changes too frequently.
The function evaluates as fast as the caching mechanism itself
Space is too tight
How to eliminate caches
Space tight--> eliminate last used caches (last referenced)
4. Expectation
Central notion: reserve your computing for opportunities to realize
potential for expanding knowledge
You may decide how much to expend re-confirming the expected
Reductions realizable through expectations:
Perceptual set: see what you expect with less effort
Surprise: heighten sensitivity to data inconsistent with
expectations
Predict and prepare
What mechanisms are implicated?
Caching
PDMs (as triggers or demons)
Relevance to learning
Confirm or disconfirm predictors
This requires setting up PDMs to fire on dis/confirmation
5. Cognitive economy revisited
Sample problem: using a world model (simulator) to answer questions
(e.g., what'd happen if 100 bombers went in there?)
Representation of this knowledge as PDMs at difft levels of abstn
Ability to generalize and cache results at one level at the
next higher level,
e.g. either as numerical tables, stat. distns, or
symbolic expressions
Ability to answer some questions appropriately for the requestor
at a high level of abstraction
KB Design
One good reason to use inheritanc is to speed knowledge
implementation, not computing performance
Using the system should result in its speedup
Storage should be cheap
Machine architecture
PDI should be cheap
PDMs should be scheduled with variable resources and
should be able to spend effort accordingly
How could propagation of changes be made efficient?
6-Nov-78 10:55:54-PST,1738;000000000001
Mail from RAND-UNIX rcvd at 7-Nov-78 1626-PST
From: Klahr at Rand-Unix
Date: 7 Nov 1978 at 1628-PST
Message-Id: <[Rand-Unix] 7-Nov-78 16:28:14.klahr>
To: rick
cc: lenat @ sumex-aim
Subject: Joint IJCAI paper
Rick,
Based on an initial scan of your outline, I think it looks
great. Some preliminary thoughts:
1. Title: Cognitive Economy in Artificial Intelligent Systems
2. Abstraction: I don't think we should delve into the military
domain of bomber simulations for the IJCAI paper. It
may turn off alot of people. The hearts domain may
similarly turn off a different group. However, since
we'll have examples from EURISKO, examples from hearts
should provide an additional example domain and will
not look central to the ideas presented. The area of
abstraction in simulations is powerful as we are, and
will, experience. This is perhaps worthy of its
own paper. If we do want to talk about abstraction
in simulations, I suggest alternative domains, eg,
ship or air traffic control, sporting events (football
strategies), international terrorism (more people
sympathetic here), appointment scheduling (as in proposal),
etc.
3. Caching: looks good.
4. Expectation-simplified processing: This is a confusing phrase.
The only alternative I can think of now is expectation-
focusing. The economy here is in terms of subsequent
analysis of good/bad consequences. Expectation-focusing
directs the analysis and diagnosis of behavior to those
heuristics that were instrumental in the resulting behavior.
Demons can be generated by heuristics to fire when the
heuristics' expectations are met/rejected. Thus demons
economize here by pinpointing heuristics that impacted
the resulting behavior.
5. The idea of forming and storing symbolic expressions deserves to
be a fourth independent cognitive economy. I feel it
is much more than a simple cache. Forming these expressions
may involve considerable pattern-matching, deductions, etc.
The resulting expression incorporates more than a simple
evaluation (such as caching functional values). In fact,
I would consider it to involve learning as well as caching.
The expressions are really meta-evaluations.
I think the paper would be a significant contribution to IJCAI. I will
be happy to participate in it.
--Phil
∂18-Nov-78 1848 DBL Caching
Rick and Phil,
Thanks for the notes. I like Rick's outline, and have some comments
on it and on Phil's remarks as well.
First, title and authors. In some sense this is not important, but
pragmatically it can have a big impact on the way a paper is received.
How about just Cognitive Economy? This enables the paper and its
concepts to be referred to tersely, and will pique the curiosity of
many potential readers. "Economics" sounds too presumptuous for the
material we have; the longer titles Phil suggests are more precise but
unwieldy. For author order, I would like to go first,
but if there is dissention we can draw lots or something. The primary
author should have the brunt of the task of preparing the article,
in any case, including content, prose, and document preparation.
The thesis that Rick states is much too strongly worded for my taste;
co-authoring with Rick is always a pleasure because he's the only
person as brash as I -- and occasionally moreso! But I really don't
want to claim that we have the final set of three keys (abstrac.,
caching, expectation-simplified processing) to represenational economy.
In fact, can we think of more?
THESIS: As often happens when I read Rick's stuff, I misunderstood it the
first time through, and as a result got an additional good idea out
of it that Rick didn't intend:
Much of what goes on today at the fore of AI can be viewed as
"expectation-simplified processing": frames, scripts, user modelling,
caching of all levels and flavors,... Here are a few poins on the
continuum:
After computing a value, cache it. Note: "value" may be a number,
a vector of numbers, an alphanumeric identifier, a vector of them...
Synthesize a function capable of efficiently computing desired values,
and cache that function.
Synthesize a whole concept data structure (frame, script...) which
contains relevant partial models of the recent situation.
There are more intermediate ones, but you see the progression from
static to dynamic, from scalar to descriptive. In all cases, the
motivation for doing this storage is (i) speed up the recognition of
(the need to do) similar computations in the future, and (ii) speed up
or even eliminate those computations when you decide they ARE relevant
and you want the values they would return. These are the two uses of
scripts, but also of cached constants (e.g., caching the value returned
by OWNED-BY, a function from CARS to PEOPLE). A better example: user models,
as they range from a single number, to a few numbers (e.g., in PARRY),
to a dynamic concept-modelling scheme.
OUTLINE:
Introduction:
Model of sys. org. should include, perhaps, agenda-like control capabilities
Model of intell. should stress the fact that knowledge acrretes, but only
occasionally shrinks (abandoning of a whole system of thought is
quite a rare event indeed. --- ask Kuhn!)
Model of computing can then, if we add the above 2 points, include this one:
The half-frame problem
In which the reasons supporting the tasks have the form "stiuation X is
not yet attained, but executing me will help you get there"
(e.g., facet f of concept C has only 2 entries)
Then at task-choosing time, if a task's reasons are out-of-date, it is
most likely that that is because some of them are no longer valid,
hence that the rating of the task will DECREASE
So, all we need do is re-evaluate the top task, get a new LOWER number
for its priority, reinsert it into the agenda, etc., and continue
until the top task remains at the top. The half-frame problem
gets its name from he fact that we do have to reevaluate some
tasks to see how the world has changed out from under them, BUT
in general we need only do this for a small number of tasks to find
the best one, not for ALL the tasks.
Idea of Expec.: another point is that expectations allow us to set up
frames in which to interpret the data, thereby making it v. quick.
Abstraction
As you know, I would like to rpesent heur. hier. as a kind of conceptual hier.
I liked the idea of using bomber simulation, and will comment again on this.
Caching
Brian Smith (MIT grad student) gave me the general idea that the lisp EVAL
function should, in general, have a second argument: the interpreter to use.
One very special case of this is where EVAL takes as its second argument
just a resource limit (time/space to expend); Bobrow and Norman discussed
an idea like this a while back. The continuum here stretches from the extreme
of GETP (i,e, if a value is stored or cached there, fine, if not give up),
to a more sophisticated inheritance search (accepting caches),
to the same thing but rejecting caches, to an even more complex deduction,
perhaps with searching disk allowed, and finally to INduction (try to
discover concepts relevant to answering the request).
The various headings Rick suggests are interrelated, and this may cause
us some trouble later, esp. if we don't watch out for it. E.g., the
updating principles constrain and are constrained by the storage ones;
When you store is constrained by Why; etc.
Expectation
As stated above, generalize this enough to include stereotyping,
of events (scripts), of situations (frames), of people (user models),...
Cognitive econ. revisited
This was quite good.
What about the future, when processor costs drop way beolow storage, though?
Phil's comments --- comments on them:
generally I ageed.
The heuristic about "better talk about Hearts, not Bombers", is so
ivory tower as to be fit material for Sat. Night Live. Unfortunately,
you are right that a good many AI researchers may feel that way. We don't,
so the hell with them. I did like your counterproposal about int'l.
terrorism, and I agree that we won't find ANY pro-terrorists at IJCAI.
Expectation-simplified processing IS awkward, but the concise replacements
generally have very negative connotations (e.g., stereotyping).
Expectation-focusing is not much better than the origianl term, in my opinion.
Let's get together and talk more about this. One alternative to that
would be for someone, e.g. me, to flesh out the outline, essentially
start writing some prose.
I am quite encouraged and think this will turn into a good paper.
Doug